package com.lw.leetcode.tree.b;

/**
 * Created with IntelliJ IDEA.
 * 树状数组
 * 面试题 10.10. 数字流的秩
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/13 16:33
 */
public class StreamRank {

    public static void main(String[] args) {
        StreamRank test = new StreamRank();
        test.track(0);
        int rankOfNumber = test.getRankOfNumber(1);
        System.out.println(rankOfNumber);
    }

    private int[] arr = new int[50002];

    public StreamRank() {
    }

    public void track(int x) {
        x++;
        for (int i = x; i < 50002; i += (-i & i)) {
            arr[i]++;
        }
    }

    public int getRankOfNumber(int x) {
        x++;
        int c = 0;
        for (int i = x; i > 0; i -= (-i & i)) {
            c += arr[i];
        }
        return c;
    }

}
